package org.alg.graph;

/**
 * Created with IntelliJ IDEA.
 * User: Administrator
 * Date: 15-5-6
 * Time: 下午11:53
 * 图是否是双色，将图的所有顶点着色，使得任意一条边的两个端点的颜色都不相同。
 */
public class TwoColor {
    private boolean[] marked;
    private boolean[] color;
    private boolean isTwoColorable=true;

    public TwoColor(Graph G){
        marked=new boolean[G.V()];
        color=new boolean[G.V()];
        for(int i=0;i<G.V();i++){
            if(!marked[i])
                dfs(G,i);
        }

    }

    private void dfs(Graph G,int v){
        marked[v]=true;
        for(int w:G.adj(v)){
            if(!marked[w]){
                color[w]=!color[v];
                dfs(G,w);
            }else if(color[w]==color[v]){
                isTwoColorable=false;
            }

        }
    }

}
